package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了85.76%的用户
 */
//func strStr(haystack string, needle string) int {
//
//	return strings.Index(haystack, needle)
//}

// KMP
/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：3 MB, 在所有 Go 提交中击败了7.24%的用户
 */
func strStr(haystack string, needle string) int {

	if len(needle) == 0 { return 0 }
	if len(haystack) < len(needle) { return -1 }

	m, n := len(haystack), len(needle)
	s, p := " " + haystack, " " + needle
	ne := make([]int, n + 1)

	for i, j := 2, 0; i <= n; i++ {
		for j > 0 && p[i] != p[j + 1] { j = ne[j] }
		if p[i] == p[j + 1] { j++ }
		ne[i] = j
	}

	for i, j := 1, 0; i <= m; i++ {
		for j > 0 && s[i] != p[j + 1] { j = ne[j] }
		if s[i] == p[j + 1] { j++ }
		if j == n { return i - n }
	}
	return -1
}

func main() {

	fmt.Println(strStr("hello", "ll"))
	fmt.Println(strStr("hello", ""))
}
